反编译原理-控制流分析
控制流分析
控制流结构恢复、变量和类型恢复是反编译器中端向后端转化最关键的两个步骤，本文讨论控制流结构恢复。
1. 编译器
主要是概述鲸书“高级编译器的设计与实现”第7章控制流分析，并且增加了一些内容，所涉及的相关论文书籍自行查找学习，还可以从维基百科了解学习。
1.1 Graph Algorithms
可以从论文"Notes on Graph Algorithms Used in Optimizing Compilers"了解学习。
1.2 CFG
ControlFlowGraph(控制流程图)，BasicBlock(基本块）、Predecessor（前驱）、Successor（后继）、Entry（入口）、Exit（出口）等概念，大部分的编译器控制流分析相关书籍论文都有介绍这些内容，还有应该熟悉了解图论中的有向图的相关知识。
1.3 BFS and DFS
BFS(广度优先搜索)和DFS(深度优先搜索)是图论中的两个概念，重点关注深度优先搜索，深度优先搜索有前序遍历、中序遍历、后序遍历三种遍历方法，前序遍历和后序遍历在控制流分析时是非常关键的两种遍历。大部分数据结构书籍中的图论都有介绍这些内容。
1.4 Dominator Tree
如果从流图的入口（Entry）结点到结点d的每一条可能的路径都经过结点n，称n是d的必经结点，或者说d支配n；如果从流图的结点d到出口（Exit）结点的每一条可能的路径都经过结点n，称n是d的后必经结点，或者说d后支配n。一种有效的表示支配结点信息的方法是用支配树（Dominator Tree)表示，构建支配树有静态和动态两种方法。
1.4.1 Static
主要有以下三种方法：
The Iterative Algorithm
可以从论文"A Simple, Fast Dominance Algorithm"学习了解，大部分编译器用这种方法构建支配树。
The Lengauer-Tarjan Algorithm
可以从论文"A Fast Algorithm for Finding Dominators in A Flowgraph"学习了解，一部分编译器用这种方法构建支配树。
The SEMI-NCA Algorithm
可以从论文"Finding Dominators in Practice"学习了解。
1.4.2 Dynamic
主要有以下三种方法：
The Sreedhar-Gao-Lee Algorithm
可以从论文"Incremental Computation of Dominator Trees"学习了解，编译器GCC实现了该算法
The Dynamic SEMI-NCA Algorithm
可以从论文"An Experimental Study of Dynamic Dominators"学习了解，是Static构建方法The SEMI-NCA Algorithm的改进版本。
The Depth-Based Search Algorithm
可以从论文"An Experimental Study of Dynamic Dominators"学习了解，最新LLVM版本实现了该算法。
1.5 Loop and SCC
编译器和反编译器在控制流分析时，需要处理循环结构，循环结构最普遍的是流图中的SCC(强连通分量)，大部分数据结构书籍中的图论都有介绍SCC(强连通分量)。
1.6 Reducible
可归约性是流图的一个非常重要的性质，假设对流图进行若干变换，该变换将子图蜕化为单个结点，归约成更简单的若干子图，如果一系列的转化最终能够把流图归约成单个结点，则称这个流图是可归约的。某些控制流模式会使得流图不可约，大概有以下几种方法处理不可约流图：
1.6.1 Node Spilt
因为传统的结点分割很容易造成流图的结点个数指数级增长，不推荐使用这种方法。
可以从论文"Controlled Node Splitting"和论文Handling Irreducible Loops: Optimized Node Splitting vs. DJ-graphs学习非传统方法的结点分割。
1.6.2 CFG Flattening
CFG Flattening（控制流平坦化），虽然常用于代码混淆，但实际上也是把不可约流图转化成可归约流图的一种方法。
1.6.3 DataFlow Analysis
对于不可约流图，还可以进行数据流分析,该内容不在本文讨论范围。
1.7 Region
由于历史原因，区间分析Region Analysis也称为Interval Analysis。区间分析将流图划分成各种类型的区域，使每一个区域蜕化成一个抽象节点，最终得到层次化、嵌套的抽象流图，该流图产生一棵控制树。
1.7.1 T1-T2 Interval
最简单、最早的区间分析，可从鲸书“高级编译器的设计与实现”第7章控制流分析了解详情。
1.7.2 Maximal Interval
区间分析使用极大区间，忽略不可归约区域，可从鲸书“高级编译器的设计与实现”第7章控制流分析了解详情。
1.7.3 Minimal Interval
更为现代的区间分析，有考虑不可归约区域，可从鲸书“高级编译器的设计与实现”第7章控制流分析了解详情。
1.8 Structural
1980年Sharir的论文"Structural Analysis: A New Approach to Flow Analysis in Optimizing Compilers"定义了结构化分析。
结构化分析是区间分析的增强版本，比区间分析能分析更多的区间类型。可从鲸书“高级编译器的设计与实现”第7章控制流分析了解该传统结构化分析。
1.9 PST/RPST
区间分析或结构化分析只能处理SESE(Single-Entry-Single-Exit) 区间类型的流图，PST/RPST就是构建只包含SESE(Single-Entry-Single-Exit) 区域类型的控制树的一种方法。
1.9.1 PST
可以从论文"The Process Structure Tree"了解学习
1.9.2 RPST
Graph Decomposition
区间分析或结构化分析的第一步骤和图论中的画图类似，都是要划分流图。图论的画图把流图划分成每一个最小组件，该最小组件称为Triconnected Components，有效表示Triconnected Components的方法是用SQPR-Tree表示。可以从论文"Application of SPQR-Trees in the Planarization Approach for Drawing Graphs"了解学习。
RPST
RPST树就是一棵层次化、每个叶子节点都是一个SESE(Single-Entry-Single-Exit) 区间类型的控制树。可以论文"The Refined Process Structure Tree" 和论文"Simplified Computation and Generalization of the Refined Process Structure Tree"了解学习，开源库codebase能构建RPST树。
2. 反编译器
反编译器进行控制流结构恢复时，所使用的算法很多来自于编译器的控制流分析。
2.1 CFG+Dominators
反编译器的控制流程图比编译器控制控制流程图结点数量更多，分析时需要更多的时间和内存。早期LLVM版本构建支配树使用静态方法Lengauer-Tarjan算法，最新LLVM版本构建支配树已使用动态方法Depth-Based Search算法。
2.2 Reducible
反编译的不可归约流图比编译器的不可约流图数量和类型更多。
2.2.1 Node Spilt teavm
实现了论文"Handling Irreducible Loops: Optimized Node Splitting vs. DJ-graphs"的结点分割算法。
2.2.2 CFG Flattening
编译器的不可约流图通常是多入口的循环，但反编译器的不可约流图有更多的类型，LLVM源码目录lib/Target/WebAssembly/的WebAssemblyFixIrreducibleControlFlow的实现类似于用控制流平坦化处理不可约循环。
2.2.3 DataFlow Analysis
数据流分析不在本文讨论范围。
2.3 Analysis
反编译器的控制流分析有迭代控制流分析、区间分析和结构化分析三种方法。
2.4 Iterative Analysis
迭代分析主要有以下三种方法：
2.4.1 Simple
最简单的控制流分析，根据模式进行归约合并，一些反编译器会使用编译器前端语法分析的一些方法。
2.4.2 CFG + Dominator
最基础的控制流分析，虽然用Simple的方法可以归约合并控制流图，但是有一些缺陷：比如假设有一个控制流的基本块，它的前驱代码位置不在它的前面，它的后继代码位置不在它的后面，则Simple方法根据模式归约合并将会出错，但如果是使用了控制流图和支配树的方法进行归约合并将不会出错。
开源反编译Retdec就使用了控制流图和支配树的方法进行控制流图重建恢复，问题在于它处理不可约流图时所使用的结点分割是传统的结点分割，导致反编译后的源码膨胀率严重，随便测试了一个百K左右的二进制文件的反编译，最后竟然生成了3-4M的c源码。
2.4.3 DFS parenthesis
DFS parenthesis特性，可以从算法导论第22章了解。开源反编译器boomerang就是用DFS parenthesis进行控制流分析。
2.5 Region Analysis
区间分析比迭代分析更有效。
2.5.1 T1-T2 Interval
axtor，采用论文"Controlled Node Splitting"的结点分割算法和T1-T2结构化分析进行控制流图重建 fernflower，开源Java反编译器，采用传统的结点分割和T1-T2结构化分析进行控制流图重建。
2.5.2 Maximal Interval
dcc是第一个使用极大化区间分析（Maximal Interval)的开源反编译器，没有考虑不可归约图，只支持16位二进制程序反编译，当然扩展支持32位/62位二进制程序反编译也不会太困难。
2.5.3 Minimal Interval
通常对不可约非正常区域，极小化区间分析方法采用将一个公共节点作为必经节点，其它节点边就必须要从控制流程图删除，并插入goto语句，另外，一些正常区域由于编译优化或代码混淆的原因，匹配规则不确定，也是无法归约的，同样是插入goto语句。
eclipse omr的区间分析实现不知道是不是极小化区间分析。
2.6 Structural Analysis
结构化分析是反编译器控制流分析最主要的分析方法。
2.6.1 Sharir Structural
鲸书“高级编译器的设计与实现”第7章控制流分析有详细说明。
2.6.2 Zadeck Structural
Zadeck Structural，GCC补丁，并没有相关论文，使用gcc后端IR RTL，由于它是用于编译器，而编译器比反编译器拥有更多的信息，因此如果要把该算法用于反编译器需要一些修改。
2.6.3 Hex-Rays Structural
IDA Pro反编译插件Hex-Rays Decompiler是反编译器的事实标准，它的结构化分析算法应该和sharir或zadeck的算法有些类似，只是对不可约非正常区域的处理方法有些不同。第14章会不完全探讨它的实现。
2.7 PST/RPST Analysis
LLVM的Region Analysis，也是SESE(Single-Entry-Single-Exit) Region Analysis，源码注释了说明其最基本的思路来自于PST/RPST ，LLVM源码目录lib/Transform/Scalar下的StructurizeCFG源文件是算法的具体实现，好像是来自早期LLVM源码目录lib/Target/AMDGPU下的AMDGPUMachineCFGStructurizer源文件。
最新LLVM源码目录lib/Target/AMDGPU下的AMDGPUMachineCFGStructurizer源文件算法在编译器后端实现，变得更加复杂。算法大概思路是把IF基本块和Else基本块都转化成IF_Then_Else基本块。
2.7.1 PST
Harpoon，构建PST树进行控制流分析。
2.7.2 RPST
abcd，java开源反编译器，用支配树来建立RPST树，好像并不能称为构建RPST树，只能称为构建控制树。
2.8 Enhanced Region Structural Analysis
传统结构化分析的扩展，传统结构化分析只能处理只包含SESE(Single-Entry-Single-Exit) 区域的流图，扩展结构化分析新定义了SESS(Single-Exit-Single-Successor) 区域类型，好像能处理部分流图是Multi-Exit区域类型的情况。
2.8.1 Type 1
可以从论文"Enhanced Structural Analysis for C Code Reconstruction from IR Code"学习了解。
2.8.2 Type 2
可以从论文"Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring"了解学习。
2.9 Normalized Region Structural Analysis
因为区间分析或结构化分析只能处理只包含SESE(Single-Entry-Single-Exit) 区间类型的流程图，因此需要把原来的控制流图转化成只包含SESE (Single-Entry-Single-Exit) 区间类型的流程图，当前主要有以下两种方法：
2.9.1 Type 1
可以从论文"Emscripten: An LLVM-to-JavaScript Compiler"学习了解。
2.9.2 Type 2
可以从论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"学习了解。
2.10 Elimination
反编译器的控制流分析，是结构化分析，是基于控制树的控制流消去法，有些类似于数据流分析。
2.10.1 Normalized
反编译器的流图的区间类型有四种类型：SESE(Single-Entry-Single-Exit) 、SEME(Single-Entry-Multi-Exit) 、MESE(Multi-Entry-Single-Exit) 、MEME(Multi-Entry-Multi-Exit) 。为了能够进行结构化分析，需要把原来的流图都转化成只包含SESE(Single-Entry-Single-Exit) 区间的流程图。
当前有三种方法：第一种，构建RPST树，然后进行结构化分析；第二种，控制流平坦化，然后用Emscripten实现的ReLooper算法进行控制流分析；第三种，使用论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"的方法进行结构化分析。
2.10.2 Structuring Acyclic Regions
如何最小化控制流图重建后goto语句的数量的大小，无环区域的简化和优化的实现非常关键。
（一）Rules Matching
根据规则进行模式匹配，开始进行类型归类时有些想当然了，如何用规则匹配进行If语句合并将在另一篇“if-else分支的识别和合并”说明。
（二）Path Finding
根据规则匹配归约合并条件语句的方法有最大的缺陷：并不能覆盖所有的规则，由于二进制代码经过编译器优化，代码混淆的原因，匹配的规则数量是不确定的，则控制流图重建后不可避免有goto语句。
因此，需要考虑一种不使用规则模式匹配的方法来进行条件归约合并，
可以使用类似于符号执行所使用的Path Finding方法进行条件语句归约合并，论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"中所使用的条件归约合并方法类似于Path Finding，论文有些晦涩，并不容易理解，有些类似于数据流分析自顶向下（Top-Down）向前问题（Forward）的到达-定值(Reaching Definitions)。
IF Regions
条件跳转区域简化和合并主要有以下两种方法
Switch Regions
Switch Regions 三种表现形式：位计算，跳转表，If跳转或二叉树If跳转。
控制流重建时主要考虑跳转表，需要考虑两种特殊的情况：case 块没有用Break语句，直接Fallthrough到下一个case 块；case 块没有用Break语句，而是使用Return语句。
Return/Finish Regions
某一无环区域有多个Return/Finish(Finish块通常用于资源释放)，编译优化后二进制代码可能会共用一个Return/Finish块，结构化分析时需要复制Return/Finish块。
Other Regions
C++异常和C运行库函数setjump()/longjump()所代表的区域，暂时不考虑。
2.10.3 Structuring Cyclic Regions
有环区域极简化和合并有两种情况：第一种，有环区域Loop和无环区域Seq相互转化；第二种，有环区域Loop三种归约类型的规则匹配：While、DoWhile、For。
对于有环区域Loop，需要考虑两种特殊情况：
第一种，前一个区域是多个Return/Finish(Multi-Exit)区域，假设前一个区域不进行复制Return/Finish块，则结构化分析归约后当前Loop区域的If条件语句将带有多个前一个区域Return/Finish块的前驱If Condition条件语句的反转not(Condition)语句；
第二种，当前Loop循环体内部多个Return/Finish(Multi-Exit)区域。这两种类型都会使得控制流重建后不可避免有goto语句，并且可读性差，大部分的反编译器是没有考虑这种情况的，比如Hex-Rays Decompiler就没有考虑这种情况。
2.11 Decompiler Paper
已经公布存在的闭源和开源反编译器相关的论文
2.11.1 Type 1
DREAM++，相关论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"；
还有相关后端优化的论文"Helping Johnny to Analyze Malware A Usability-Optimized Decompiler and Malware Analysis User Study"。
DREAM， 相关论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"。
Hex-Rays Decompiler，相关论文"Decompilers and Beyond White Paper"，还有相关中端IR的PPT "Decompiler internals: microcode"。
Phoenix，相关论文"Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring"。
Mirtoc，相关论文"Enhanced Structural Analysis for C Code Reconstruction from IR Code"。
2.11.2 Type 2
fcd，开源，相关论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"。
reko，开源，相关论文"Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring"。
Emscripten，开源，相关论文"Emscripten: An LLVM-to-JavaScript Compiler"。
dcc，开源，相关论文"Reverse Compilation Techniques"。
axtor，开源，相关论文"Decompilation of LLVM IR"。
Boomerang，开源，相关论文"Structuring Assembly Programs" 还有变量和类型重建的相关论文"SSA for Decompilation"。
BAP-0.8，开源，相关论文"Structural Analysis: A New Approach to Flow Analysis in Optimizing Compilers"。
SmartDec/Snowman，开源，相关论文"SmartDec: Approaching C++ Decompilation"。
RetDec，开源，相关论文"Static Decompilation of Unobfuscated Native Code"。
总结
主流的重新构建控制流图的方法都是对控制流程图进行结构化分析生成控制树，然后尝试将函数流程图的可归约的一小部分与已知模式匹配，并在不起作用时使用goto语句。
因此，反编译二进制程序时控制流结构恢复后goto语句的数量是衡量反编器表现的一个重要标准。然而，论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"开发了一种称为模式无依赖的控制流结构分析新技术，它重新构建控制流图时没有使用任何预定义模式，控制流结构恢复后没有goto语句。
综上所述，实现没有goto语句的C语言反编译器是可能的，该反编译器重建流图的大概操作简述如下:
Stage 1
构建RPST树，确保控制流图只包含SESE(Single-Entry-Single-Exit) 区域类型。
Stage 2
结构化分析，在控制流图中查找区域，生成控制树。
Stage 3
路径查找(Path Finding)，计算每个块的到达条件。
Stage 4
简化和合并控制流语句。
附录
fcd实现相关文章：
1.The Region Problem
http://zneak.github.io/fcd/2016/02/17/structuring.html
2.The Loop Problem
http://zneak.github.io/fcd/2016/02/24/seseloop.html
3.Revisiting Structurization
http://zneak.github.io/fcd/2016/11/25/revisiting-regions.html
- End -
看雪ID：vasthao
https://bbs.pediy.com/user-422740.htm
本文由看雪论坛 vasthao 原创
转载请注明来自看雪社区
热门图书推荐：
热门技术文章推荐：
公众号ID：ikanxue
官方微博：看雪安全
商务合作：wsc@kanxue.com